package problem980;

//980.不同路径3
//https://leetcode.cn/problems/unique-paths-iii/
class Solution {
    int ret = 0;
    int n,m,count;
    int[] xx = {1, -1, 0, 0};
    int[] yy = {0, 0, 1, -1};
    boolean[][] st;
    public int uniquePathsIII(int[][] grid) {
        n = grid.length;
        m = grid[0].length;
        st = new boolean[n][m];
        int x = 0, y = 0;
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                if(grid[i][j] == 1) {
                    x = i;
                    y = j;
                }
                if(grid[i][j] == 0) {
                    count++;
                }
            }
        }
        st[x][y] = true;
        dfs(grid, x, y, 0);
        return ret;
    }
    public void dfs(int[][] grid, int x, int y, int step) {
        if(grid[x][y] == 2 && step == count+1) {
            ret++;
            return;
        }
        for(int i = 0; i<4; i++) {
            int dx = x + xx[i];
            int dy = y + yy[i];
            if(dx >= 0 && dx < n && dy >= 0 && dy < m && !st[dx][dy] && grid[dx][dy] != -1) {
                st[dx][dy] = true;
                dfs(grid, dx, dy, step+1);
                st[dx][dy] = false;
            }
        }
    }
}

/*
0 1
2 0
*/